package cn.yuemouren.suanfa;

/**
 * @Author: Timi
 * @Description: 插入排序
 * @Date: 2020/7/23 13:29
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {1,7,2,4,5,8,15,9};
        sort(arr);
        for (int i : arr)
            System.out.print(i+",");
        System.out.println("-------------");
    }

    /**
     * 每次都是从最后往前面比
     * @param arr
     */
    private static void sort(int[] arr){

        for (int i = 1; i < arr.length; i++){
            int insertValue = arr[i];
            //被插入的位置
            int index = i - 1;
            while(index >= 0 && insertValue < arr[index]){
                //将把 arr[index] 向后移动
                arr[index + 1] = arr[index];
                //index向前移动
                index--;
            }
            arr[index + 1] = insertValue;
        }
    }
}
